package main

import "fmt"

// 约瑟夫问题：
// 设编号为1.2.3....n 的n个人围坐一圈，约定编号为k的人从1开始报数，数到m的人出列，
// 它的下一位又从1开始报数，数到m的人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
func main() {
	var head *Node //头节点
	for i := 1; i <= 10; i++ {
		if head == nil {
			head = AddElement(nil, i)
		} else {
			head = AddElement(head, i)
		}
	}
	Print(head)

	var k int = 2
	var m int = 3
	var seq []interface{} = make([]interface{}, 0)
	fmt.Printf("[约瑟夫问题] k=%d m=%d \n", k, m)
	head = GetNewHeadByK(head, k)
	fmt.Printf("新的head =%v \n", head)

	//循环查找和删除
	for {
		ele, h := Joseph(head, m)
		head = h        //新的head
		if ele != nil { //找到了则添加到结果集中
			seq = append(seq, ele)
			fmt.Printf("删除ele=%v 后的链表为： \n", ele)
			Print(head)
		} else {
			break
		}
	}
	fmt.Println("出列的编号是：")
	for _, no := range seq {
		fmt.Printf("=>%d\t", no)
	}

}

type Node struct {
	Ele  interface{}
	Next *Node
}

// GetNewHeadByK
//
//	@Description: 根据k找到新的head
//	@param head
//	@param k
//	@return h 新的head
func GetNewHeadByK(head *Node, k int) (h *Node) {
	if head == nil { //头节点为空,则返回nil
		return nil
	}
	current := head
	for {
		if current.Ele == k { //找到k节点,返回新的head
			return current
		}
		if current.Next == head { // 如果到最后一个节点，break
			break
		}
		current = current.Next //移动
	}
	panic("没有找到k节点")

}

// Joseph
//
//	@Description: Joseph问题，删除第m个节点，返回新的head
//	@param head
//	@param m
//	@return ele
//	@return h 新的head
func Joseph(head *Node, m int) (ele interface{}, h *Node) {
	var sort int = 0
	for {
		if head == nil { //说明删除完毕，break
			break
		}
		sort++
		if sort == m { //如果找到第m个节点，跳出
			fmt.Printf("出列编号=%v ", head.Ele)
			ele = head.Ele
			break
		}
		head = head.Next // 移动
	}

	//如果找到，则删除该节点，返回新的head
	if ele != nil {
		h, _ = DeleteElement(head, head.Ele)
		return ele, h
	}

	//没有找到，直接返回
	return ele, head
}

// PlayJoseph 见图PlayJoseph.png
//
//	@Description:
//	@param head
//	@param start
//	@param count
func PlayJoseph(head *Node, start int, count int) {
	if head == nil {
		return
	}
	if head.Next == nil {
		return
	}

	// | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
	//   h									  t
	//将tail 指向最后一个节点,效果如上图
	tail := head
	for {
		if tail.Next == head { //说明tail已经是最后一个节点了
			break
		}
		tail = tail.Next //tail向后移动
	}

	//	找到start,则移动start-1 次
	// | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
	//   t   h
	//	让head和tail分别移动start-1次，start = 2,则移动1次,如上图
	for i := 1; i <= (start - 1); i++ {
		head = head.Next
		tail = tail.Next
	}

	for {
		// | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
		//           t   h
		// 再移动count-1次, 如上图，count=3,则移动2次
		for i := 1; i <= (count - 1); i++ {
			head = head.Next
			tail = tail.Next
		}
		//删除head
		// | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
		//           t   	 h
		//           t.n-----|
		fmt.Println("出列-->", head.Ele)
		head = head.Next
		tail.Next = head

		if head == tail { //说明删除完毕
			break
		}

	}

}

// AddElement
//
//	@Description:
//	@param head
//	@param ele
//	@return h 新的head
func AddElement(head *Node, ele interface{}) (h *Node) {
	node := &Node{
		Ele: ele,
	}
	if head == nil { //如果头节点为空，则创建一个头节点
		head = node
		return head
	} else {
		if head.Next == nil { //如果头节点的下一个节点为空
			head.Next = node //头节点的next指向node
			node.Next = head //node的next指向头节点,形成环形
			return head
		} else {
			temp := head
			for {
				if temp.Next == head { //找到最后一个节点
					break
				}
				temp = temp.Next //移动
			}
			temp.Next = node //将最后一个节点的next指向node
			node.Next = head //node的next指向头节点,形成环形
		}
		return head
	}

}

// DeleteElement
//
//	@Description:  删除节点
//	@param head
//	@param ele
//	@return n
//	@return err
func DeleteElement(head *Node, ele interface{}) (n *Node, err error) {
	if head == nil || head.Next == head {
		return nil, fmt.Errorf("删除失败，链表为空或只有一个节点")
	}
	temp := head
	helper := head

	// 如果头节点就是要删除的节点
	if temp.Ele == ele {
		// 找到链表的最后一个节点
		for helper.Next != head {
			helper = helper.Next
		}
		// 将最后一个节点的Next指向头节点的下一个节点
		helper.Next = temp.Next
		// 更新头节点
		head = temp.Next
		return head, nil
	}

	// 遍历链表查找要删除的节点
	for temp.Next != head {
		if temp.Next.Ele == ele {
			// 找到要删除的节点
			temp.Next = temp.Next.Next
			return head, nil
		}
		temp = temp.Next //向后移动
	}

	// 如果没有找到要删除的节点
	return head, fmt.Errorf("删除失败，没有找到要删除的节点")
}

// Print
//
//	@Description:
//	@param head
func Print(head *Node) {
	if head == nil {
		fmt.Println("链表为空")
		return
	}
	temp := head
	if temp.Next == nil {
		return
	}
	for {
		fmt.Printf("ele=%v | ptr=%p | next=%p \n", temp.Ele, temp, temp.Next)
		if temp.Next == head { //最后一个节点
			break
		}
		temp = temp.Next //向后移动
	}
}
